#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

//test on 1337 online judge and pass all the test
class Solution1 {
    public:
        bool canJump(int A[], int n) {
            int jump = 0;
            int i = 0;
            int count = 0;
            if (n == 1) return true;    // i miss this when submit
            while (i < n-1 && count < n-1) {
                int move = 0;
                int max = 0;
                for (int j = i+1; j <= i + A[i]; j++) {
		    if (j >= n-1) return true;
                    if (j + A[j] > max) {
                        max = j + A[j];
                        move = j;
                    }
	//				cout << move << endl;
                }
                jump++;
                i = move;
                count++;
            }
            return count == n-1 ? false : true;
        }
};

class Solution {
public:
    bool canJump(int A[], int n) {
        int cur = 0;
        if (n == 1) return true;
        while (cur < n) {
            int prev = cur;
            int next = cur;
	    int maxStep = 0;
            for (int i = cur; i <= cur + A[cur] ;i++) {
                if (i + A[i] >= n-1) return true;
		if (maxStep < i + A[i]) {
		    maxStep = i + A[i];
		    next = i;
		}
            }   
            cur = next;
            if (next == prev) return false;
        }   
    }   
};


int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    int test[] = {3,2,1,0,4};
    bool result = mySolution.canJump(test, sizeof(test)/sizeof(int));
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
